분할 상환 분석(Amortized Analysis)

수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균

확률을 사용하지 않는 방법으로 평균비용 분석(avergae-case analysis)와는 다름

- 총계 분석; T(n) upper bound

n개의 연산의 최악의 경우 전체적인 시간복잡도 T(n)을 이용해 연산당 평균 비용(=분할상환 비용; amortized cost)

T(n)/n을 구함

결산 방법, 잠재 비용 방법과 달리 “모든 연산에 대해서 동일하게 적용한다."

void MultiPop(Stack stack, int k){

while(!stack.empty() && k>0){

stack.pop();

k--;

}

Pop, Push, MultiPop 연산이 n개의 시퀀스로 이루어져 있을 경우,

MultiPop 연산이 n회 반복되는 O(n^2)의 시간 복잡도를 가진다.

하지만, 빈 스택의 경우, Push를 수행한 횟수 만큼가 Pop, MultiPop이 최대로 수행될 수 있는 횟수이다.

따라서 연산 시퀀스는 총 O(n)의 시간 복잡도를 가진다.

분할 상환 비용: O(n)/n=O(1)

- 결산 방법(Accounting Method)

결산 방법에서는 연산에 대해서 각각 다른 비용(분할 상환 비용)을 부과한다.

크레딧(credit)이라는 자료구조에 어떤 연산의 분할 상환 비용과 실제 비용의 차이를 누적하고, 이를 반영한다.

Σni=1(ĉ i)≥Σni=1ci $\Sigma_{i=1}^n(\hat c_i) \geq \Sigma_{i=1}^nc_i$ ĉ i $\hat c_i$ :분할상환비용, ci $c_i$ :실제비용

- 잠재 비용 방법(Potential Method)

결산 방법처럼 크레딧의 형태로 표현하는 대신 잠재 비용 방법은 비용의 차이를

미래의 연산들의 비용으로 지불하기 위해 사용될 수 있다.

Φ $\Phi$ : 비용함수(Potential Function) ĉ i=ci+Φ(Di)−Φ(Di−1) $\hat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1})$ Φ(Dn)≥Φ(D0) $\Phi(D_n)\geq \Phi(D_0)$

동적 테이블(Dynamic Table)

확장(Extension)

void TableInsert(Table table, int x){

if(table.size==0){

table.extend(1);

table.size=1;

}

if(T.num==T.size){

int newSize=table.size*2;

// 복사 연산(deep-copy included) 및 메모리 해제(Memory free)

table.extend(newSize);

table.size*=2;

}

table.insert(x);

table.num++;

}

빈 Table에 대해서 TableInsert 연산을 n번 수행할 때,

c_i에 대해서 i-1번의 복사가 필요(deep copy) ; 복사는 c_i가 2의 거듭제곱일 때만 발생

table 적재률 α(T)=T.num/T.size $\alpha(T)=T.num/T.size$ Φ(T)= $\Phi(T)=$ 2⋅T.num−T.size⋅ $2\cdot T.num-T.size\cdot$ ; α(T)≥1/2 $\alpha(T) \geq 1/2$ 일 때 T.size/2−T.num $T.size/2-T.num$ ; α(T)<1/2 $\alpha(T) < 1/2$ 일 때

위와 같은 잠재함수를 사용하는 경우,

동적 테이블에 n개의 연산으로 구성된 임의의 시퀀스에 대해

걸리는 총 시간은 O(n)이다.